#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 数据结构定义
typedef struct {
    int weight;
    double value;
} Item;

typedef struct {
    int *selected;
    double total_value;
    int total_weight;
    double time_cost;
    int memory_error;  // 内存错误标志
} Result;

// 工具函数
int max_int(int a, int b) {
    return (a > b) ? a : b;
}

// 检查内存需求是否合理
int check_memory_feasible(int n, int capacity) {
    // 估算需要的内存（字节）
    long long memory_needed = (long long)(n + 1) * (capacity + 1) * sizeof(int);
    long long memory_limit = 16LL * 1024 * 1024 * 1024;  // 16GB限制
    
    printf("    估算内存需求: %.2f GB\n", memory_needed / (1024.0 * 1024.0 * 1024.0));
    
    if (memory_needed > memory_limit) {
        printf("    内存需求超过限制(16GB)，跳过执行\n");
        return 0;
    }
    
    return 1;
}

// 从文件读取测试数据
Item* load_test_data(const char* filename, int* n) {
    FILE *file = fopen(filename, "r");
    if (file == NULL) {
        printf("无法打开文件 %s\n", filename);
        return NULL;
    }
    
    // 读取物品数量
    fscanf(file, "%d", n);
    
    // 分配内存并读取物品数据
    Item *items = malloc(*n * sizeof(Item));
    
    for (int i = 0; i < *n; i++) {
        fscanf(file, "%d %lf", &items[i].weight, &items[i].value);
    }
    
    fclose(file);
    return items;
}

// 动态规划法求解0-1背包问题（优化版本）
Result dp_knapsack(Item items[], int n, int capacity) {
    Result result = {0};
    result.selected = calloc(n, sizeof(int));
    result.memory_error = 0;
    
    // 检查内存可行性
    if (!check_memory_feasible(n, capacity)) {
        result.total_value = -1;
        result.memory_error = 1;
        return result;
    }
    
    printf("    开始分配DP表内存...\n");
    
    // 创建DP表
    int **dp = malloc((n + 1) * sizeof(int*));
    if (dp == NULL) {
        printf("    DP表主数组分配失败\n");
        result.total_value = -1;
        result.memory_error = 1;
        return result;
    }
    
    // 逐行分配内存并检查
    for (int i = 0; i <= n; i++) {
        dp[i] = calloc(capacity + 1, sizeof(int));
        if (dp[i] == NULL) {
            printf("    DP表第%d行分配失败\n", i);
            // 释放已分配的内存
            for (int j = 0; j < i; j++) {
                free(dp[j]);
            }
            free(dp);
            result.total_value = -1;
            result.memory_error = 1;
            return result;
        }
        
        // 每分配1000行显示一次进度
        if (i % 1000 == 0 && i > 0) {
            printf("    已分配 %d/%d 行\n", i, n);
        }
    }
    
    printf("    DP表分配完成，开始填充...\n");
    
    // 填充DP表（价值乘以100转为整数处理）
    for (int i = 1; i <= n; i++) {
        // 每处理1000个物品显示一次进度
        if (i % 1000 == 0) {
            printf("    处理进度: %d/%d 个物品\n", i, n);
        }
        
        for (int w = 1; w <= capacity; w++) {
            if (items[i-1].weight <= w) {
                int value_int = (int)(items[i-1].value * 100);
                int option1 = dp[i-1][w];
                int option2 = dp[i-1][w - items[i-1].weight] + value_int;
                dp[i][w] = max_int(option1, option2);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    
    printf("    DP表填充完成，开始回溯...\n");
    
    result.total_value = dp[n][capacity] / 100.0;  // 转回浮点数
    
    // 回溯找出选择的物品
    int w = capacity;
    int remaining_value = dp[n][capacity];
    for (int i = n; i > 0 && remaining_value > 0; i--) {
        if (remaining_value != dp[i-1][w]) {
            result.selected[i-1] = 1;
            result.total_weight += items[i-1].weight;
            remaining_value -= (int)(items[i-1].value * 100);
            w -= items[i-1].weight;
        }
    }
    
    printf("    回溯完成，释放内存...\n");
    
    // 释放内存
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

// 输出结果到文件
void output_result_to_file(const char* filename, Item items[], int n, Result result) {
    FILE *file = fopen(filename, "w");
    if (file == NULL) {
        printf("无法创建输出文件 %s\n", filename);
        return;
    }
    
    if (result.total_value < 0) {
        if (result.memory_error) {
            fprintf(file, "算法未执行（内存不足或分配失败）\n");
        } else {
            fprintf(file, "算法未执行（其他错误）\n");
        }
        fclose(file);
        return;
    }
    
    // 输出选择的物品
    fprintf(file, "选择的物品（编号 重量 价值）:\n");
    for (int i = 0; i < n; i++) {
        if (result.selected[i]) {
            fprintf(file, "%d %d %.2f\n", i + 1, items[i].weight, items[i].value);
        }
    }
    
    // 输出总重量、总价值和时间开销
    fprintf(file, "总重量: %d\n", result.total_weight);
    fprintf(file, "总价值: %.2f\n", result.total_value);
    fprintf(file, "时间开销: %.6f 秒\n", result.time_cost);
    
    fclose(file);
}

int main() {
    printf("=== 动态规划法测试器（16GB内存限制版本） ===\n");
    
    // 物品数量数组
    int item_counts[] = {1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 
                        20000, 40000, 80000, 160000, 320000};
    int num_item_counts = sizeof(item_counts) / sizeof(item_counts[0]);
    
    // 背包容量数组
    int capacities[] = {10000, 100000, 1000000};
    int num_capacities = sizeof(capacities) / sizeof(capacities[0]);
    
    printf("内存限制: 16GB\n");
    printf("开始动态规划法测试...\n\n");
    
    // 对每个物品数量
    for (int i = 0; i < num_item_counts; i++) {
        int item_count = item_counts[i];
        char data_filename[100];
        sprintf(data_filename, "items_%d.txt", item_count);
        
        printf("加载数据文件: %s\n", data_filename);
        
        int n;
        Item *items = load_test_data(data_filename, &n);
        
        if (items == NULL) {
            printf("跳过文件: %s\n", data_filename);
            continue;
        }
        
        // 对每个背包容量进行测试
        for (int j = 0; j < num_capacities; j++) {
            int capacity = capacities[j];
            
            printf("  测试容量 %d (物品数量: %d):\n", capacity, n);
            
            clock_t start = clock();
            Result result = dp_knapsack(items, n, capacity);
            clock_t end = clock();
            
            result.time_cost = ((double)(end - start)) / CLOCKS_PER_SEC;
            
            // 生成输出文件名
            char output_filename[200];
            sprintf(output_filename, "dp_%d_%d.txt", item_count, capacity);
            
            output_result_to_file(output_filename, items, n, result);
            
            if (result.total_value >= 0) {
                printf("    完成 (%.6f秒, 价值=%.2f)\n", result.time_cost, result.total_value);
            } else {
                if (result.memory_error) {
                    printf("    跳过执行（内存不足）\n");
                } else {
                    printf("    跳过执行（其他错误）\n");
                }
            }
            
            if (result.selected != NULL) {
                free(result.selected);
            }
        }
        
        free(items);
        printf("\n");
    }
    
    printf("动态规划法测试完成！\n");
    return 0;
}